using Nemerle.Collections;

using Nextem.String;

namespace Renraku.Compiler {
	public type CILGraphBody = GraphBody [CILArg];
	
	public module CILGraph {
		public FromCIL(cil : Assembly [CILBody]) : Assembly [CILGraphBody] {
			cil.MapMethods(Graphize)
		}
		
		Graphize(cil : CILBody) : CILGraphBody {
			// Iterate over the body and find branches, making a list of block refs
			def findRefs(body : CILBody, accum = []) {
				match(body) {
					| [] => accum
					| (_, inst) :: tail =>
						findRefs(
							tail, 
							match(inst) {
								| Branch((op, _, _), _, taken, not) =>
									if(op == Op.Nil) taken :: accum
									else not :: taken :: accum
								| _ => accum
							}
						)
				}
			}
			def refs = findRefs(cil).Sort((a, b) => a.CompareTo(b));
			
			// Build a hashtable of nodes, walking over the body.
			// It recurses, popping references off the list and keeping the
			// start position for the block (the key), while accumulating instructions
			// in cur.  Once the position is >= the next ref, it means the end of the
			// block.  addImplicitBranch creates an unconditional branch to the next
			// block if the current block doesn't end with a branch, to keep the graph
			// flowing properly.
			def nodes = Hashtable();
			def splitNodes(body : CILBody, refs, start = 0, cur = []) {
				def addImplicitBranch(cur : list [Inst [CILArg, int]], pos) {
					match(cur) {
						| Branch :: _ => cur
						| _ => Inst.Branch((Op.Nil, null, null), false, pos, 0) :: cur 
					}
				}
				
				match(body) {
					| [] =>
						when(!cur.IsEmpty) nodes[start] = cur.Reverse()
					| (pos, _) :: _ when !refs.IsEmpty && pos >= refs.Head =>
						def cur = addImplicitBranch(cur, pos);
						nodes[start] = cur;
						splitNodes(body, refs.Tail, refs.Head)
					| (_, inst) :: tail =>
						splitNodes(tail, refs, start, inst :: cur)
				}
			}
			splitNodes(cil, refs);
			
			// Iterate over each node and each instruction in the node and make
			// CILGraphBody instructions from the original CILBody instructions.
			// This needs to be rolled into a map function in Inst itself.
			// Branch destinations are nulled out so that the next pass can add the
			// proper references.
			def mapNodes(key : int, value : list [Inst [CILArg, int]]) {
				def mapInsts(inst : Inst [CILArg, int]) : Inst [CILArg, CILGraphBody] {
					| Push(src) => Inst.Push(src)
					| Pop(dest) => Inst.Pop(dest)
					| Conv(ovf, size, dest, src) => Inst.Conv(ovf, size, dest, src)
					| Assign(dest, src) => Inst.Assign(dest, src)
					| LoadAddr(dest, src) => Inst.LoadAddr(dest, src)
					| LoadElem(size, dest, arr, index) => Inst.LoadElem(size, dest, arr, index)
					| StoreElem(size, arr, index, value) => Inst.StoreElem(size, arr, index, value)
					| StoreInd(size, dest, src) => Inst.StoreInd(size, dest, src)
					| Unary(op, dest, src) => Inst.Unary(op, dest, src)
					| Binary(op, ovf, dest, opers) => Inst.Binary(op, ovf, dest, opers)
					| Branch(cond, unsigned, _, _) => Inst.Branch(cond, unsigned, null, null)
					| Return(val) => Inst.Return(val)
					| Breakpoint => Inst.Breakpoint()
				}
				(key, CILGraphBody(value.Map(x => mapInsts(x))))
			}
			def graphNodes = nodes.Map(mapNodes);
			
			// Walk over the nodes and fix their branch references to point to the
			// proper objects.  It refers to the original 'nodes' hashtable to get
			// the block start addresses and uses them as the keys to the graphNodes
			// table.
			def remapNodes(key : int, value : CILGraphBody) {
				match(value.Insts) {
					| Branch as branch :: _ =>
						match(nodes[key]) {
							| Branch((op, _, _), _, taken, not) :: _ =>
								branch.Taken = graphNodes[taken];
								unless(op == Op.Nil)
									branch.NotTaken = graphNodes[not]
							| _ => ()
						}
					| _ => ()
				}
				(key, value)
			}
			def finalNodes = graphNodes.Map(remapNodes);
			// Hand back the first block of the method.  The rest will flow.
			finalNodes[0]
		}
	}
}
